/*
 *Description:
 *User:laohHu
 *Created with Intellij IDEA 2025
 *Data:2025.05.21
 *Time:14:43
 */

//KPM算法
public class Main {

    //Next数组的实现
    public static void getNext(String sub,int[] getNext){

        getNext[0] = -1;
        getNext[1] = 0;
        int k = 0;
        for (int j = 2; j < sub.length(); ) {
            if(k == -1 || sub.charAt(j -1) == sub.charAt(k)){
                getNext[j] = k+1;
                k++;
                j++;
            } else{
                k = getNext[k];
            }
        }
    }

    //KMP方法实现
    public static int KPM(String str,String sub,int pos){

        //先判断子串和主串和位置是否合法
        if(str == null || sub == null) return -1;
        int strLen = str.length();
        int subLen = sub.length();
        if(strLen == 0 || subLen == 0) return -1;
        if(pos < 0 || pos > strLen) return -1;

        //创建Nxet数组
        int[] next = new int[sub.length()];
        getNext(sub,next);

        //判断主串和子串元素，遍历
        int i = pos;//主串位置
        int j = 0;//子串位置
        while(i < strLen && j < subLen){
            if(j == -1||str.charAt(i) == sub.charAt(j)){
                i++;
                j++;
            } else{
                j = next[j];
            }
        }
      //次数跳出while循环，说明子串或主串已经遍历完
        if(j >= subLen){
            return i - j;
        } else{
            return -1;
        }

    }
    public static void main(String[] args) {
        System.out.println( KPM("abababcabcd","abcd",0));
        System.out.println( KPM("abababcabcd","abc",0));
        System.out.println( KPM("abababcabcd","ab",0));

    }
}